The present invention relates to an associative memory of the type commonly known as a CAM.
As is well known in the art, such memories comprise an array of memory cells, each holding a data bit, the cells being arranged in rows and columns. Each row normally holds a word, for example of 32 bits. Data can be read and written into a CAM in a manner similar to that for a random access memory (RAM). In addition, a CAM cell has an additional function in that it provides a match signal indicating whether a data word input to the CAM array matches a data word already stored in the array. This function can be used to quickly check the contents of the CAM for a word match, by inputting a data word and generating a match signal for any row of the CAM in which all bits of the data word match the bits stored in memory cells of that row. When the match signal for the row is high, this indicates that the input data word is stored in the CAM array.
To perform this function, each CAM cell generates a local or cell match signal which indicates if data input to the cell matches the data already stored in the cell. In order to determine whether or not a complete word is matched, these local match signals need to be somehow combined to generate a match signal for a row. It will readily be appreciated, that as soon as one of the cells fails to match, the match signal for the row is low.
FIG. 1 illustrates output circuitry for a CAM row which represents one known way of generating the match signal for a row. It is assumed herein that there are 32 cells in each row of the CAM, representing a 32 bit word to be matched. Each cell of the row is associated with a respective drive output transistor 20, 21 . . . 232 which receives at its gate the local match signal m0, m1 . . . m32. A precharge transistor 4 receives an active low precharge signal PC at its gate for precharging. Holding circuitry 6 serves to assist in holding the match signal high, in a manner which is known in the art.
According to this arrangement, the match outputs m0, m1 . . . m32 drive the output transistors 20, 21 . . . 232 in parallel. If any one of the local match signals is low, the output signal MATCH at a so-called common node 8 will be caused to fall.
A disadvantage of this arrangement is that it requires precharge and hold circuitry as represented by transistor 4 and holding circuitry 6, the precharge transistor 4 being required to precharge the common node 8 high in between each match cycle. The precharge logic requires timing analysis etc., which makes it potentially complex to operate.
According to an alternative known arrangement, the cell match signals are supplied in pairs to respective AND gates. The outputs of these AND gates are likewise supplied in pairs to a subsequent logic stage of AND gates. Thus, the match signals are combined in pairs to generate a final logical value for the match signal for each row. For a row of 32 bits, six stages of logic gates are required. Although this overcomes the problems associated with the need for precharge circuitry, the distance between the stages is large, requiring large drive transistors to encompass the distances. However, it is frequently the case that the drive transistors are not utilised, for the simple reason that many of the match outputs will be zero. Thus, this design is inherently redundant.
It is an aim of the present invention to provide an associative memory in which the match cell is generated in an easier and more efficient manner.
According to the present invention there is provided an associative memory comprising an array of memory cells arranged in rows and columns, each row comprising a plurality of segments each of which comprises a set of said memory cells, wherein each memory cell has compare circuitry for comparing input data with data stored therein and for generating a cell match signal when said input data matches said stored data and match signal combining circuitry for receiving a match signal from a preceding cell in the set and operable to generate a logical value dependent on the match signal of the current cell and the match signal of the preceding cell whereby each segment generates a resultant segment logical value, the memory further comprising combinatorial logic circuitry associated with each row for combining said resultant segment logical values to generate a final output match signal for that row.
For a better understanding of the present invention and to show how the same may be carried into effect, reference will now be made by way of example to the accompanying drawings, in which: